package leetcode_700;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *@author 周杨
 *FindKClosestElements_658 找出一个数组中接近k的n个元素
 *describe:用二分查找定位 再扩大搜索区间 AC 38%
 *2018年9月28日 上午11:13:14
 */
public class FindKClosestElements_658 {
	public static void main(String[] args) {
		System.out.println(Arrays.binarySearch(new int[] {1,2,3},6));
		FindKClosestElements_658 test=new FindKClosestElements_658();
		//test.findClosestElements(new int[] {0,0,1,2,3,3,4,7,7,8}, 3, 5);
		test.findClosestElements(new int[] {0,1,2,2,2,3,6,8,8,9},5, 9);
	}
	
	/**
	 * describe:
	 * 2018年9月28日 上午10:26:12
	 */
	public List<Integer> findClosestElements(int[] arr, int k, int x) {
		 List<Integer> res=new ArrayList<Integer>();
	        int index=Arrays.binarySearch(arr, x);
	        int left,right;
	        if(index<0) {
	        	index=-index-1;
	        }
	        if(index==0) {
        		left=0;
        		right=1;
        	}
        	else if(index>=arr.length-1) {
        		left=arr.length-2;
        		right=arr.length-1;
        	}
        	else {
        		if(Math.abs(arr[index+1]-x)<Math.abs(arr[index-1]-x)) {
        			left=index;
        			right=index+1;
        		}
        		else {
        			left=index-1;
        			right=index;
        		}
        	}
	        while(k>0) {
	        	if(left<0) {
	                ++right;
	        		--k;
	        		continue;
	        	}
	        	if(right==arr.length) {
	                --left;
	        		--k;
	        		continue;
	        	}
	        	if(arr[right]-x<x-arr[left]) {
	        		++right;
	        	}
	        	else {
	        		--left;
	        	}
	        	--k;
	        }
	        for(int i=left+1;i<right;++i) {
	        	res.add(arr[i]);
	        }
	        return res;
    }
}
